#include<iostream>
using namespace std;
const int N = 1010;
int l[N], r[N], p[N];
int dis[N];
int n, m;
void dfs(int u, int d)
{
	dis[u] = d;
	if (l[u])dfs(l[u], d + 1);
	if (r[u])dfs(r[u], d + 1);
}
int get_lca(int a, int b)
{
	if (dis[a] < dis[b])return get_lca(b, a);
	while (dis[a] > dis[b])a = p[a];
	while (a != b) {
		a = p[a];
		b = p[b];
	}
	return a;
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			int a, b;
			cin >> a >> b;
			l[i] = a, r[i] = b;
			if (a != -1)p[a] = i;
			if (b != -1)p[b] = i;
		}
		dfs(1, 0);
		while (m--) {
			int a, b;
			cin >> a >> b;
			int c = get_lca(a, b);
			cout << dis[a] + dis[b] - 2 * dis[c] << endl;
		}
	}
	return 0;
}